/*
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at 
 * 
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 *  
 */

using System;
using java = biz.ritter.javapi;
using org.apache.commons.collections;

namespace org.apache.commons.collections.iterators
{

    /**
     * An Iterator that can traverse multiple iterators down an object graph.
     * <p>
     * This iterator can extract multiple objects from a complex tree-like object graph.
     * The iteration starts from a single root object.
     * It uses a <code>Transformer</code> to extract the iterators and elements.
     * Its main benefit is that no intermediate <code>List</code> is created.
     * <p>
     * For example, consider an object graph:
     * <pre>
     *                 |- Branch -- Leaf
     *                 |         \- Leaf
     *         |- Tree |         /- Leaf
     *         |       |- Branch -- Leaf
     *  Forest |                 \- Leaf
     *         |       |- Branch -- Leaf
     *         |       |         \- Leaf
     *         |- Tree |         /- Leaf
     *                 |- Branch -- Leaf
     *                 |- Branch -- Leaf</pre>
     * The following <code>Transformer</code>, used in this class, will extract all
     * the Leaf objects without creating a combined intermediate list:
     * <pre>
     * public Object transform(Object input) {
     *   if (input is Forest) {
     *     return ((Forest) input).treeIterator();
     *   }
     *   if (input is Tree) {
     *     return ((Tree) input).branchIterator();
     *   }
     *   if (input is Branch) {
     *     return ((Branch) input).leafIterator();
     *   }
     *   if (input is Leaf) {
     *     return input;
     *   }
     *   throw new ClassCastException();
     * }</pre>
     * <p>
     * Internally, iteration starts from the root object. When next is called,
     * the transformer is called to examine the object. The transformer will return
     * either an iterator or an object. If the object is an Iterator, the next element
     * from that iterator is obtained and the process repeats. If the element is an object
     * it is returned.
     * <p>
     * Under many circumstances, linking Iterators together in this manner is
     * more efficient (and convenient) than using nested for loops to extract a list.
     * 
     * @since Commons Collections 3.1
     * @version $Revision: 7135 $ $Date: 2011-06-04 20:58:43 +0200 (Sa, 04. Jun 2011) $
     * 
     * @author Stephen Colebourne
     */
    public class ObjectGraphIterator : java.util.Iterator<Object>
    {

        /** The stack of iterators */
        protected readonly ArrayStack stack = new ArrayStack(8);
        /** The root object in the tree */
        protected Object root;
        /** The transformer to use */
        protected Transformer transformer;

        /** Whether there is another element in the iteration */
        protected bool hasNextJ = false;
        /** The current iterator */
        protected java.util.Iterator<Object> currentIterator;
        /** The current value */
        protected Object currentValue;
        /** The last used iterator, needed for remove() */
        protected java.util.Iterator<Object> lastUsedIterator;

        //-----------------------------------------------------------------------
        /**
         * Constructs an ObjectGraphIterator using a root object and transformer.
         * <p>
         * The root object can be an iterator, in which case it will be immediately
         * looped around.
         * 
         * @param root  the root object, null will result in an empty iterator
         * @param transformer  the transformer to use, null will use a no effect transformer
         */
        public ObjectGraphIterator(Object root, Transformer transformer)
            : base()
        {
            if (root is java.util.Iterator<Object>)
            {
                this.currentIterator = (java.util.Iterator<Object>)root;
            }
            else
            {
                this.root = root;
            }
            this.transformer = transformer;
        }

        /**
         * Constructs a ObjectGraphIterator that will handle an iterator of iterators.
         * <p>
         * This constructor exists for convenience to emphasise that this class can
         * be used to iterate over nested iterators. That is to say that the iterator
         * passed in here contains other iterators, which may in turn contain further
         * iterators.
         * 
         * @param rootIterator  the root iterator, null will result in an empty iterator
         */
        public ObjectGraphIterator(java.util.Iterator<Object> rootIterator)
            : base()
        {
            this.currentIterator = rootIterator;
            this.transformer = null;
        }

        //-----------------------------------------------------------------------
        /**
         * Loops around the iterators to find the next value to return.
         */
        protected void updateCurrentIterator()
        {
            if (hasNextJ)
            {
                return;
            }
            if (currentIterator == null)
            {
                if (root == null)
                {
                    // do nothing, hasNext will be false
                }
                else
                {
                    if (transformer == null)
                    {
                        findNext(root);
                    }
                    else
                    {
                        findNext(transformer.transform(root));
                    }
                    root = null;
                }
            }
            else
            {
                findNextByIterator(currentIterator);
            }
        }

        /**
         * Finds the next object in the iteration given any start object.
         * 
         * @param value  the value to start from
         */
        protected void findNext(Object value)
        {
            if (value is java.util.Iterator<Object>)
            {
                // need to examine this iterator
                findNextByIterator((java.util.Iterator<Object>)value);
            }
            else
            {
                // next value found
                currentValue = value;
                hasNextJ = true;
            }
        }

        /**
         * Finds the next object in the iteration given an iterator.
         * 
         * @param iterator  the iterator to start from
         */
        protected void findNextByIterator(java.util.Iterator<Object> iterator)
        {
            if (iterator != currentIterator)
            {
                // recurse a level
                if (currentIterator != null)
                {
                    stack.push(currentIterator);
                }
                currentIterator = iterator;
            }

            while (currentIterator.hasNext() && hasNextJ == false)
            {
                Object next = currentIterator.next();
                if (transformer != null)
                {
                    next = transformer.transform(next);
                }
                findNext(next);
            }
            if (hasNextJ)
            {
                // next value found
            }
            else if (stack.isEmpty())
            {
                // all iterators exhausted
            }
            else
            {
                // current iterator exhausted, go up a level
                currentIterator = (java.util.Iterator<Object>)stack.pop();
                findNextByIterator(currentIterator);
            }
        }

        //-----------------------------------------------------------------------
        /**
         * Checks whether there are any more elements in the iteration to obtain.
         * 
         * @return true if elements remain in the iteration
         */
        public bool hasNext()
        {
            updateCurrentIterator();
            return hasNextJ;
        }

        /**
         * Gets the next element of the iteration.
         * 
         * @return the next element from the iteration
         * @throws NoSuchElementException if all the Iterators are exhausted
         */
        public Object next()
        {
            updateCurrentIterator();
            if (hasNextJ == false)
            {
                throw new java.util.NoSuchElementException("No more elements in the iteration");
            }
            lastUsedIterator = currentIterator;
            Object result = currentValue;
            currentValue = null;
            hasNextJ = false;
            return result;
        }

        /**
         * Removes from the underlying collection the last element returned.
         * <p>
         * This method calls remove() on the underlying Iterator and it may
         * throw an UnsupportedOperationException if the underlying Iterator
         * does not support this method. 
         * 
         * @throws UnsupportedOperationException
         *   if the remove operator is not supported by the underlying Iterator
         * @throws IllegalStateException
         *   if the next method has not yet been called, or the remove method has
         *   already been called after the last call to the next method.
         */
        public void remove()
        {
            if (lastUsedIterator == null)
            {
                throw new java.lang.IllegalStateException("Iterator remove() cannot be called at this time");
            }
            lastUsedIterator.remove();
            lastUsedIterator = null;
        }

    }
}